
/*
Description:
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

*/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
	/*
	This problem has a typical solution using Dynamic Programming. 
	We define the state P[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. 
	Then the state equations are:

    P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
    P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
    P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.
	*/
	bool isMatch(string s, string p) {
		int m = s.length(), n = p.length();
		vector<vector<bool> > dp(m + 1, vector<bool>(n + 1, false));
		dp[0][0] = true;
		for (int i = 0; i <= m; i++)
			for (int j = 1; j <= n; j++)
				if (p[j - 1] == '*')
					dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
				else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
				return dp[m][n];
	}

	/*
	1.'.' is easy to handle. if p has a '.', it can pass any single character in s except '\0'.
	2.'' is a totally different problem. if p has a '' character, it can pass any length of first-match characters in s including '\0'.
	*/
	bool matchFirst(const char *s, const char *p) {
		return (*p == *s || (*p == '.' && *s != '\0'));
	}

	bool isMatch0(const char *s, const char *p) {
		if (*p == '\0') return *s == '\0';	//empty

		if (*(p + 1) != '*') {//without *
			if (!matchFirst(s, p)) return false;
			return isMatch(s + 1, p + 1);
		}
		else { //next: with a *
			if (isMatch(s, p + 2)) return true;    //try the length of 0
			while (matchFirst(s, p))       //try all possible lengths 
				if (isMatch(++s, p + 2))return true;
		}
	}
	
	bool isMatch1(string s, string p) 
	{
		auto itp = p.begin();
		auto its = s.begin();
		for (; its!=s.end(); ++its)
		{
			if (itp == p.end())
			{
				break;
			}

			if ((*itp == *its) || (*itp == '.'))
			{
				++itp;
				continue;
			}
			else
			{
				auto it = itp;
				if (*it == '*')
				{
					--it;
					if ((*it == *its) || (*it == '.'))
					{
						continue;
					}
					else
					{						
						++itp;
						if ((*itp == *its) || (*itp == '.'))
						{
							++itp;
							continue;
						}
						else 
						{
							break;
						}
					}
				}
				else
				{
					++it;
					if (*it == '*')
					{
						if ((*itp == *its) || (*itp == '.'))
						{
							continue;
						}
						else
						{
							++it;
							if (*it == *its)
							{
								itp = it;
								++itp;
							}
							else
							{
								break;
							}
						}
					}
					else
					{
						break;
					}
				}																
			}
		}

		if (itp != p.end()) 
		{
			if (*itp == '*')
			{
				++itp;
				auto iits = its;
				--iits;
				if (itp != p.end())
				{
					if (*iits == *itp)
					{
						++itp;
					}
				}
			}				
		}

		if ((its != s.end()) || (itp != p.end()))
		{
			return false;
		}
		else
		{
			return true;
		}
	}
};

int _isMatch()
{
	typedef struct {
		string s;
		string p;
	} CASE;

	CASE case1{ "aa","a" };
	CASE case2{ "aa","a*" };
	CASE case3{ "ab",".*" };
	CASE case4{ "aab","c*a*b" };
	CASE case5{ "mississippi","mis*is*p*." };
	CASE case6{ "aaa","a*a" };
	CASE case7{ "aaa","ab*a" };
	CASE case8{ "aaa","ab*a*c*a" };
	CASE testcase = case8;
	Solution solu;
	bool match;
	
	match = solu.isMatch(testcase.s, testcase.p);

	cout << "s: " << testcase.s << endl;
	cout << "p: " << testcase.p << endl;
	cout << "match: " << match << endl;

	return 0;
}